﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    /*
     * Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 21 elements in this set.

How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?

     * 
     * */
    class Problem72 : IProblem
    {
        public string Calculate()
        {
            //najultrapizdarija problem ikad
            //trebalo je nimalo mašte

            //svaki broj ce imat onoliko tih frakcija koliki mu je phi

            int limit = 1000000;

            var totient = new Problem69().CalculateTotients(limit);

            long sum = 0;

            foreach (var i in totient)
                sum += i;

            sum--;

            return sum.ToString();
        }
    }
}
